|
|
x1
|
Recherche
On parcourt séquentiellement le noeud où on se trouve. Si la valeur courante est la valeur recherchée, on a terminé.
Si la valeur actuelle est inférieure, il ne reste qu'à chercher dans le i-éme fils.
Sinon, c'est qu'elle est supérieure. Deux cas se présentent.
S'il y a encore une valeur dans le noeud on s'y rend et on réitère le processus.
Par contre, s'il s'agissait de la dernière valeur du noeud il ne reste qu'à cherché dans le dernier fils.
Si durant la recherche on doit recherché dans un fils à NULL, la valeur n'existe pas dans l'arbre. On retourne la position du fils et le noeud courant.
Insertion
L'insertion utilise la recherche. Si la valeur n'existe pas, on peut l'insèrer. Soit P et i respectivement le noeud et la position retournés par la recherche.
Si P est plein, on crée un nouveau noeud et on l'attache comme i-ème fils de P.
Sinon, on insère directement à la i-ème position de P en faisant éventuellement des décalages.
Suppression
La suppression use de la recherche. Elle est logique pour présérvé la propriété top-down.
